//package offer;
//
//public class offer36 {
//}
//class Node
//{
//    public int val;
//    public Node left;
//    public Node right;
//
//    public Node() {}
//
//    public Node(int _val) {
//        val = _val;
//    }
//
//    public Node(int _val,Node _left,Node _right) {
//        val = _val;
//        left = _left;
//        right = _right;
//    }
//}
//class Solution36 {
//   Node pre  = null;
//   Node head = null;
//
//    public Node treeToDoublyList(Node root) {
////        首先这是个中序遍历转成双向链表的过程
//        if(root==null) return null;
//        dfs(root);
//        head.left = pre;
//        pre.right = head;
//    return head;
//    }
//
//    private void dfs(Node root) {
//        if(root==null) return;
//        dfs(root.left);
//        if(pre!=null) pre.right  =root;
//        else head = root;
//        root.left = pre;
//        pre = root;
//        dfs(root.right);
//    }
//}